#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums)
    {
        tmp.resize(nums.size());
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }

    void mergeSort(vector<int>& nums, int left, int right)
    {
        if(left >= right)
            return;
        int mid = (left+right)/2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid+1, right);

        int cur1 = left, cur2 = mid+1, i = 0;
        while(cur1 <= mid && cur2 <= right)
        {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
        }
        while(cur1 <= mid)  tmp[i++] = nums[cur1++];
        while(cur2 <= right)    tmp[i++] = nums[cur2++];

        for(int i=left; i<=right; i++)
        {
            nums[i] = tmp[i-left];
        }
    }
};
